#include<stdio.h>
#include<malloc.h>

typedef struct a{
  int item;
  struct a *next,*prev;
} node;

node *append(node *,int);
node *extend(node *);
node *insert(node *,int,int);
node *pop(node *,int);
node *rem(node *,int);
node *sort(node *);
node *rev(node *);
int count(node *);
int ind(node *,int);

node *append(node *head,int val){
  node *temp = head,*new = (node *)malloc(sizeof(node));
  new->item = val;
  new->next = NULL;
  if(temp == NULL) {
    new->prev = NULL;
    return new;
  }
  while(temp->next != NULL) temp = temp->next;
  temp->next = new;
  new->prev = temp;
  return head;
}

node *extend(node *head){
  int n,i;
  printf("Enter number of elements to extend into the list : ");
  scanf("%d",&n);
  for(i = 0;i<n;i++){
    int t;
    printf("Element : ");
    scanf("%d",&t);
    head = append(head,t);
  }
  return head;
}

node *insert(node *head,int pos,int value){
  node *temp = head, *new = (node *)malloc(sizeof(node));
  new->item = value;
  new->next = NULL;
  if(temp == NULL){
    new->prev = NULL;
    return new;
  }
  if(pos == 0){
    new->next = head;
    head->prev = new;
    new->prev = NULL;
    return new;
  }
  int count = 0;
  while(count < (pos-1) && temp->next != NULL){
  count++;
  temp = temp->next;
  }
  if(temp == NULL) printf("WTF?");
  printf("Hehe\n");
  printf("%d",temp->item);
  new->next = temp->next;
  if(temp->next != NULL){
  temp->next->prev = new;
  }
  temp->next = new;
  new->prev = temp;
  return head;
}

node *pop(node *head,int pos){
  node *temp = head;
  if (temp == NULL){
    printf("Empty List!\n"); 
    return NULL;
  }
  if(pos == 0){
    printf("Value popped : %d",head->item);
    temp = temp->next;
    temp->prev = NULL;
    return temp;
  }
  int count = 0;
  while(count < (pos-1) && temp != NULL){
    count++;
    temp = temp->next;
  }
  if(temp == NULL) printf("IndexError : list.pop(x) : x out of range\n");
  printf("Value popped : %d\n",temp->next->item);
  temp->next = temp->next->next;
  temp->next->prev = temp;
  return head;
}

node *rem(node *head,int value){
  node *temp = head;
  if(temp->item == value){
    temp = temp->next;
    temp->prev = NULL;
    return temp;
  }
  while(temp->item != value && temp != NULL){
    temp = temp->next;
  }
  if(temp == NULL){
    printf("ValueError : list.remove(x) : x not in list\n");
    return head;
  }
  temp = temp->prev;
  temp->next = temp->next->next;
  temp->next->prev = temp;
  return head;
}
node *sort(node *head){
  int len = count(head);
  if(len < 2) return head;
  else{
    int i = 0,j = 0;
    node *first,*second;
    for(i = 0;i<len;i++){
      first = head;
      second = head->next;
      while(second!= NULL){
        if(first->item > second->item){
          int temp = first->item;
          first->item = second->item;
          second->item = temp;
        }
        first = first->next;
        second = second->next;
      }
    }
  }
  return head;
}
node *rev(node *head){
  node *temp = head,*newlist = NULL;
  while(temp->next != NULL) temp = temp->next;
  while(temp != NULL){
    newlist = append(newlist,temp->item);
    temp = temp->prev;
  }
  return newlist;
}
int count(node *head){
  int count = 0;
  while(head != NULL){
    count++;
    head = head->next;
  }
  return count;
}
int ind(node *head,int val){
  int inde = 0;
  while(head->item != val && head != NULL){
    inde++;
    head = head->next;
  }
  return inde;  
}

void print(node *head){
  if(head != NULL) printf("[%d",head->item);
  head = head->next;
  while(head != NULL){ 
    printf(",%d",head->item);
    head = head->next;
  }
  printf("]\n");
}

int main(void){
  node *head = NULL;
  int i,j,k;
  while(1){
    printf("Array Lists : \n1. Insert\n2. Append\n3. Extend\n4. Pop\n5. Remove\n6. Index\n7. Reverse\n8. Sort\n9. Length\n10. Exit\n?: ");
    scanf("%d",&k);
    switch(k){
      case 1: 
        printf("Enter value to insert : ");
        scanf("%d",&i);
        printf("Enter index : ");
        scanf("%d",&j);
        head = insert(head,j,i);
        break;
      case 2:
        printf("Enter Value to append: ");
        scanf("%d",&i);
        head = append(head,i);
        break;
      case 3:
        head = extend(head);
        break;
      case 4:
        printf("Enter index to pop : ");
        scanf("%d",&i);
        head = pop(head,i);
        break;
      case 5:
        printf("Enter Value to remove : ");
        scanf("%d",&i);
        head = rem(head,i);
        break;
      case 6:
        printf("Enter Value to find : ");
        scanf("%d",&i);
        j = ind(head,i);
        if(j>=0) printf("Element found at : %d\n",j);
        else printf("ValueError : list.index(x) : x not in list\n");
        break;
      case 7:
        head = rev(head);
        break;
      case 8:
        head = sort(head);
        break;
      case 9:
        i = count(head);
        printf("Number of elements : %d\n",i);
        break;
      case 10:
        return 0;
      default: 
        printf("Please select from among the options...");
    }
    print(head);
  }
  return 0;
}
